package com.study.suanfa.shu.erchashu;

/**
 * @description: ThreadBinaryTree1Test  线索化二叉树
 * @date: 2020/12/4 18:10
 * @author: hcm
 * @version: 1.0
 */
class ThreadBinaryTree1Test {

    public static void main(String[] args) {
        HeroNode1 root = new HeroNode1(1, "草帽路飞");
        HeroNode1 node2 = new HeroNode1(3, "索隆");
        HeroNode1 node3 = new HeroNode1(6, "娜美");
        HeroNode1 node4 = new HeroNode1(8, "罗兵");
        HeroNode1 node5 = new HeroNode1(10, "乔巴");
        HeroNode1 node6 = new HeroNode1(14, "乌索普");
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);


        BinaryTree1 binaryTree1 = new BinaryTree1();
        binaryTree1.setRoot(root);
        binaryTree1.threadNode();

        HeroNode1 leftNode = node5.getLeft();
        System.out.println(leftNode);
    }
}

/**
 * 构建二叉树
 */
class BinaryTree1 {
    private HeroNode1 root;

    /**
     * 线索化指向当前节点的前驱节点
     */
    private HeroNode1 pre =null;

    public HeroNode1 getRoot() {
        return root;
    }

    /**
     * 线索化
     * @param node  当前需要线索化的节点
     */
    public void threadNode(HeroNode1 node){
        //node == null 不能线索化
        if(node == null){
            return;
        }
        //线索化左子树
        threadNode(node.getLeft());
        //线索化当前节点

        //处理当前节点的前驱节点
        if(node.getLeft() == null){
            //当前节点的左指针指向前驱节点
            node.setLeft(pre);
            //修改当前节点左指针类型,说明指向前驱节点
            node.setLeftType(1);
        }
        //处理后继节点
        if(pre != null && pre.getRight() == null){
            pre.setRight(node);
            pre.setRightType(1);
        }
        //每处理一个节点后让当前节点是下一个节点的前驱节点
        pre = node;

        //线索化右子树
        threadNode(node.getRight());

    }

    public void setRoot(HeroNode1 root) {
        this.root = root;
    }

    public BinaryTree1() {

    }

    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        }
    }

    public void preOrderSeach(int no) {
        if (this.root != null) {
            System.out.println("查找第" + no + "个节点为： " + this.root.preOrderSerch(no));
        }
    }

    /**
     * 递归删除节点
     */
    public void delNode(int no) {
        if (root == null) {
            System.out.println("空树无法删除");
            return;
        }
        if (this.root.getNo() == no) {
            root = null;
        } else {
            root.delNode(no);
        }
    }


    public void threadNode() {
        threadNode(root);
    }
}
class HeroNode1 {

    private int no;
    private String name;
    private HeroNode1 left;
    private HeroNode1 right;

    /**
     * 如果leftType == 0 表示指向的是左子树，如果为1则表示指向前驱节点
     * 如果rightType == 0 表示指向的是右子树，如果1表示指向后继节点
     */
    private int leftType;
    private int rightType;

    public HeroNode1(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode1 getLeft() {
        return left;
    }

    public void setLeft(HeroNode1 left) {
        this.left = left;
    }

    public HeroNode1 getRight() {
        return right;
    }

    public void setRight(HeroNode1 right) {
        this.right = right;
    }

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    @Override
    public String toString() {
        return "HeroNode1{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    /**
     * 前序遍历方法
     */
    public void preOrder() {
        //输出当前节点
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    /**
     * 中序遍历
     */
    public void midOrder() {
        if (this.left != null) {
            this.left.midOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.midOrder();
        }

    }

    /**
     * 后序
     */
    public void postOrder() {
        if (this.left != null) {
            this.left.midOrder();
        }

        if (this.right != null) {
            this.right.midOrder();
        }
        System.out.println(this);
    }

    /**
     * 前序遍历查找
     */
    public HeroNode1 preOrderSerch(int no) {
        //比较当前节点
        if (this.no == no) {
            return this;
        }
        HeroNode1 res = null;
        if (this.left != null) {
            res = this.left.preOrderSerch(no);
        }
        if (res != null) {
            return res;
        }
        if (this.right != null) {
            res = this.right.preOrderSerch(no);
        }
        if (res != null) {
            return res;
        }
        return res;
    }

    public void delNode(int no) {
        if (this.left != null && this.left.no == no) {
            this.left = null;
            return;
        }
        if (this.right != null && this.right.no == no) {
            this.right = null;
            return;
        }
        if (this.left != null) {
            this.left.delNode(no);
        }
        if (this.right != null) {
            this.right.delNode(no);
        }
    }
}
